package com.cdream.basic.algorithm.leetcode.string;

public class Question31 {
    public void nextPermutation(int[] nums) {
        int n = nums.length;
        int k = n - 1;
        // 前一个数比后一个数大的情况下就往前移动
        while (k - 1 >= 0 && nums[k] <= nums[k - 1]) k--;
        if (k == 0) {
            reverse(nums, 0, n - 1);
        } else {
            int u = k;
            while (u < n - 1 && nums[u + 1] > nums[k - 1]) {
                u++;
            }
            swap(nums, k - 1, u);
            reverse(nums, k, n - 1);


        }
    }

    private void reverse(int[] nums, int l, int r) {
        int start = l, end = r;
        while (start < end) {
            swap(nums, start, end);
            start++;
            end--;
        }
    }

    private void swap(int[] nums, int j, int k) {
        int i = nums[j];
        nums[j] = nums[k];
        nums[k] = i;
    }
}
